Packet switching involves the transmission of data in packets through a data network. Fixed sized packets are referred to as cells. Each block of end-user data that is to be transmitted is divided into cells. A unique identifier, a sequence number and a destination address are attached to each cell. The cells are independent and may traverse the data network by different routes. The cells may incur different levels of propagation delay, or latency, caused by physical paths of different length. The cells may be held for varying amounts of delay time in buffers in intermediate switches in the network. The cells also may be switched through different numbers of packet switches as the cells traverse the network, and the switches may have unequal processing delays caused by error detection and correction.
Historically, a bufferless crossbar has been used as the switching fabric of a virtual output queue (VOQ) switch, which suffers from the scheduling bottleneck that limits the switch's scalability. It has been shown that the scheduling bottleneck can be overcome by replacing the bufferless crossbar with an internally buffered crossbar (IBX), where a small size buffer is located at each crosspoint of the internally buffered crossbar (VOQ+IBX). Specifically, it has been shown that for each internal buffer, a size as small as two cells (or packets) can bring at least two benefits: (1) the ability to perform the scheduling task by each input/output arbiter independently; and (2) the ability to achieve a theoretically guaranteed 100% throughput under any admissible traffic load, with each input or output having an arbitration complexity of O(Log N) per time slot, for an N×N switch.
However, as the switch size grows, the number of internal buffers increases quadratically, resulting in greater difficulties in the implementation of the buffered crossbar. Thus, the physical scalability of a buffered crossbar using current silicon technology is limited. Therefore, there is a need in the art for improved fixed-sized packet switches. In particular, there is a need for a highly scalable switch architecture having a bufferless, non-blocking interconnecting network between the input ports and the output ports of the switch. More particularly, there is a need for a switch that does not require the use of a crossbar containing internal buffers.